//  给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

var letterCombinations = function(digits) {
    const k = digits.length;
    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    if (!k) return [];
    if (k === 1) return map[digits].split("");

    const res = [],
        path = [];
    backtracking(digits, k, 0);
    return res;

    function backtracking(n, k, a) {
        if (path.length === k) {
            res.push(path.join(""));
            return;
        }
        for (const v of map[n[a]]) {
            path.push(v);
            backtracking(n, k, a + 1);
            path.pop();
        }

    }
};

var letterCombinations = function(digits) {
    let res = [];
    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    if (digits.length == 0) { return [] };
    if (digits.length == 1) { return map[digits].split("") };
    change([], 0)
    return res

    function change(path, a) {
        if (path.length == digits.length) {
            res.push(path.join(''))
            return;
        }
        for (k of map[digits[a]]) {
            path.push(k);
            change(path, a + 1)
            path.pop();
        }
    }
};